/*
* 2010
* Authors: Sergey Lapin <lapanoid@gmail.com>
* Feedback Arc Set class
*/

#pragma once
#include "fas_share.h"
#include "fas_numerator.h"
#include <boost/utility.hpp>

class IsProperty {
  public:
  bool virtual operator()(Vertex, const Graph &) = 0;
};

class IsSink : public IsProperty {
  public:
  bool operator()(Vertex v, const Graph &worker)
  {
      return out_degree(v, worker) == 0;
  }
  IsSink(){}
};

class IsSource : public IsProperty {
  public:
  bool operator()(Vertex v, const Graph &worker)
  {
      return in_degree(v, worker) == 0;
  }
  IsSource(){}
};

class FasGreedy : noncopyable
{
public:
    static bool   HaveCycle          (const Graph &worker);
    static void   MakeAcyclicGreedy  (Graph &worker);
    static void   VertexIndexation   (Graph &worker);        
private:
    // delete edges that perform condition of leftward arcs in incoming 
    // vertical sequence            

    static size_t GetNumberOfDigits  (size_t number);
    static void   EdgeIntersect      (list<Vertex_Number> &vertex_seq, FasDirnumerator &dirnum,
                                      Graph &worker);
    static Vertex FindMaxDelta       (const Graph &worker);
    static bool   LeftArc            (Vertex_Number left, Vertex_Number right, 
                                      list<Vertex_Number> &vertex_seq);   
    static int    CalcDelta          (Vertex v, const Graph &worker);	
    static void   DeleteByProperty   (Graph &worker, 
                                      IsProperty *isproperty,
                                      bool IsReverse,
                                      list<Vertex> *vertex_seq = NULL);
    // safe vertices and edges deleting
    static void   ClearAndRemove     (Vertex v, Graph &worker);

    // main GR algorithm procedure     
    static void	GR_procedure(list<Vertex_Number> *num_seq, FasDirnumerator &dirnum, Graph &worker);   
};